package com.lishem.carl._07tree;

import com.lishem.common.TreeNode;


/**
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
 * <p>
 * 给定两个整数数组inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，
 * <p>
 * 请你构造并返回这颗 二叉树 。
 * <p>
 * 示例 1:
 * <p>
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * <p>
 * 输出：[3,9,20,null,null,15,7]
 * <p>
 * 示例 2:
 * <p>
 * 输入：inorder = [-1], postorder = [-1]
 * <p>
 * 输出：[-1]
 */
public class _22LetCode106_从中序与后序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int[] postorder, int inLeft, int inRight, int posLeft, int posRight) {
        if (inLeft == inRight) {
            return new TreeNode(inorder[inLeft]);
        }
        if (inRight < inLeft) {
            return null;
        }
        int rootVal = postorder[posRight];
        TreeNode root = new TreeNode(rootVal);
        int rootIndexIn = -1;
        for (int i = inLeft; i <= inRight; i++) {
            if (rootVal == inorder[i]) {
                rootIndexIn = i;
                break;
            }
        }
        root.left = buildTree(inorder, postorder, inLeft, rootIndexIn - 1, posLeft, posLeft + rootIndexIn - 1 - inLeft);
        root.right = buildTree(inorder, postorder, rootIndexIn + 1, inRight, posLeft + rootIndexIn  - inLeft, posRight - 1);
        return root;
    }

    public static void main(String[] args) {
        _22LetCode106_从中序与后序遍历序列构造二叉树 sol = new _22LetCode106_从中序与后序遍历序列构造二叉树();
        TreeNode treeNode1 = sol.buildTree(new int[]{3, 2, 1}, new int[]{3, 2, 1});
        TreeNode treeNode2 = sol.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        TreeNode treeNode3 = sol.buildTree(new int[]{-1}, new int[]{-1});
    }
}
